package leetcode.year2021.month9;

import org.w3c.dom.NodeList;

public class _30_01MergeTwoLists21 {
  public static void main(String[] args) {
    ListNode listNode1 = new ListNode(1);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(1);

    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;

    ListNode result = mergeTwoLists(listNode1, listNode4);
    while (result != null){
      System.out.println(result.val);
      result = result.next;
    }

  }

  public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    if (l1 == null){
      return l2;
    }
    if (l2 == null){
      return l1;
    }

    ListNode head;
    if (l1.val < l2.val){
     head = l1;
     l1 = l1.next;
    } else {
      head = l2;
      l2 = l2.next;
    }

    ListNode ans = head;

    while (l1 != null || l2 != null){
      if (l1 == null){
        head.next = l2;
        break;
      } else if (l2 == null){
        head.next = l1;
        break;
      } else if (l1.val < l2.val){
        ListNode temp = l1;
        l1 = l1.next;
        head.next = temp;
        head = head.next;
      } else {
        ListNode temp = l2;
        l2 = l2.next;
        head.next = temp;
        head = head.next;
      }
    }

    return ans;

  }

   public static class ListNode {
     int val;
     ListNode next;

     ListNode() {
     }

     ListNode(int val) {
       this.val = val;
     }

     ListNode(int val, ListNode next) {
       this.val = val;
       this.next = next;
     }
   }
  /**

   将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

   输入：l1 = [1,2,4], l2 = [1,3,4]
   输出：[1,1,2,3,4,4]
   示例 2：

   输入：l1 = [], l2 = []
   输出：[]
   示例 3：

   输入：l1 = [], l2 = [0]
   输出：[0]
    

   提示：

   两个链表的节点数目范围是 [0, 50]
   -100 <= Node.val <= 100
   l1 和 l2 均按 非递减顺序 排列
   */
}
